/*
 * @lc app=leetcode.cn id=117 lang=cpp
 *
 * [117] 填充每个节点的下一个右侧节点指针 II
 */

// @lc code=start
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution
{
public:
    Node *connect(Node *root)
    {
        if (!root)
            return root;
        vector<Node *> vec[2];
        vec[0].push_back(root);
        int flag = 0;
        while (!vec[0].empty() || !vec[1].empty())
        {
            int i = 1;
            for (; i < vec[flag].size(); i++)
            {
                vec[flag][i - 1]->next = vec[flag][i];
                if (vec[flag][i - 1]->left)
                {
                    vec[1 - flag].push_back(vec[flag][i - 1]->left);
                }
                if (vec[flag][i - 1]->right)
                {
                    vec[1 - flag].push_back(vec[flag][i - 1]->right);
                }
            }
            if (vec[flag][i - 1]->left)
            {
                vec[1 - flag].push_back(vec[flag][i - 1]->left);
            }
            if (vec[flag][i - 1]->right)
            {
                vec[1 - flag].push_back(vec[flag][i - 1]->right);
            }
            vec[flag].clear();
            flag = 1 - flag;
        }
        return root;
    }
};
// @lc code=end
